package hot100;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class isValid {
    public static Map<Character, Character> map = new HashMap<>();

    static {
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
    }

    public boolean isValid(String s) {

        if (map.get(s.charAt(0)) == null) {
            return false;
        }

        LinkedList<Character> characters = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) != null) {
                characters.push(s.charAt(i));
            } else {
                if (characters.size() == 0) {
                    return false;
                }
                if (!map.get(characters.pop()).equals(s.charAt(i))) {
                    return false;
                }
            }
        }

        return characters.size() == 0;
    }
}
